Cloud computing is growing in popularity. A cloud service provider operates one or more data centers to provide computing or data storage services to customers. Each data center typically includes a plurality of host machines. Customers run virtual machines on the host machines for performing the customer's desired computing task. Multiple virtual machines may run simultaneously on one host machine.
While cloud services open up new possibilities for customers and service providers, they introduce new challenges. For example, a server or host machine has a limited capacity and there must be control over virtual machine assignments to that server or host machine. Additionally, virtual machine requests arrive randomly in time. Virtual machine instances may be running at one moment and stopped at the next. Any number of virtual machine requests may arrive at any particular scheduling interval. The randomness of arrival of new virtual machine requests and the randomness of a length of time during which a virtual machine will be running present challenges for assigning virtual machine requests to host machines in an efficient manner.